package com.leet.tree;

import java.util.ArrayList;
import java.util.List;

public class SortedListToBST {
    List<Integer> list = new ArrayList<>();
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        TreeNode bst = buildBST(list,0,list.size()-1);
        return bst;
    }
    public TreeNode buildBST(List<Integer> list,int l,int r){
        int mid = (l+r+1)/2;
        TreeNode root = new TreeNode(list.get(mid));
        // 如果左子树还能坚持的下去的话
        if(l <= mid-1){
            root.left = buildBST(list,l,mid-1);
        }
        if(r >= mid+1){
            root.right = buildBST(list,mid+1,r);
        }
        return root;
    }
}
